# 给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
#  有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
#  只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
#  返回 图中最大连通组件的大小 。
#
#  示例 1：
# 输入：nums = [4,6,15,35]
# 输出：4
#
#  示例 2：
# 输入：nums = [20,50,9,63]
# 输出：2
#
#  示例 3：
# 输入：nums = [2,3,6,7,4,12,21,39]
# 输出：8
import collections
import math
from typing import List


class UnionFindSet:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, node: int) -> int:
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1: int, node2: int) -> None:
        p1, p2 = self.find(node1), self.find(node2)
        if p1 != p2:
            if self.size[p1] < self.size[p2]:
                p1, p2 = p2, p1
            self.parent[p2] = p1
            self.size[p1] += self.size[p2]


class Solution:
    def largestComponentSize2(self, nums: List[int]) -> int:
        """
        将数组的每个元素进行因数分解，并将有相同因素的元素使用dict存起来(key:因数   value: 有相同因素 key 的所有元素的下标组成的集合)
        最后使用并查集合并dict的元素
        :param nums:
        :return:
        """
        def factors(a: int) -> set:
            """
            计算a的所有因数
            :param num:
            :return:
            """
            ans = set()
            for i in range(1, int(math.sqrt(a)) + 1):
                if not a % i:
                    ans.add(i)
                    ans.add(a // i)
            return ans
        n = len(nums)
        factor = collections.defaultdict(list)
        for i, num in enumerate(nums):
            fac = factors(num)
            for f in fac:
                if f != 1:
                    factor[f].append(i)
        uf = UnionFindSet(n)
        for f in factor:
            for i in range(1, len(factor[f])):
                uf.union(factor[f][i], factor[f][i - 1])
        return max(uf.size)

    def largestComponentSize1(self, nums: List[int]) -> int:
        """
        两两判断是否互质，如果不互质就并查集进行合并(超时)
        :param nums:
        :return:
        """
        def ishuzhi(num1: int, num2: int) -> bool:
            for i in range(2, min(num1, num2) + 1):
                if num1 % i == 0 and num2 % i == 0:
                    return False
            return True

        uf = UnionFindSet(len(nums))
        for i in range(len(nums)):
            for j in range(i + 1, len(nums), 1):
                if not ishuzhi(nums[i], nums[j]):
                    uf.union(i, j)
        return max(uf.size)

    def largestComponentSize(self, nums: List[int]) -> int:
        return self.largestComponentSize2(nums)


if __name__ == "__main__":
    nums = [2, 3, 6, 7, 4, 12, 21, 39]
    print(Solution().largestComponentSize(nums))
